package DLX;

import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

/**
 * Routines to solve Sudoku using DLX.
 */
public class DLXSudokuSolver implements SudokuSolver {

    private static final int BUF_SIZE = 324;

    private static final int COLUMN_CONTAINS_OFFSET = 81;

    private static final int ROW_CONTAINS_OFFSET = 162;

    private static final int REGION_CONTAINS_OFFSET = 243;

    private static Object[] LABELS;
    private byte[] decodedResult;

    /**
     * Initialize a new DLX-based Sudoku solver
     */
    public DLXSudokuSolver() {
        LABELS = generateLabels();
    }

    /**
     * Determine whether or not this is a valid Sudoku.
     * 
     * @param puzzle
     *            the puzzle to check
     */
    public boolean isValidSudoku(byte[] puzzle) {

        if (!SudokuUtils.isPuzzleLegal(puzzle))
            return false;
        if (SudokuUtils.isPuzzleComplete(puzzle))
            return true;

        // Check that the Sudoku property holds; i.e. there is one and only one
        // solution

        CountingOnlyDLXResultProcessor resultProcessor = new CountingOnlyDLXResultProcessor();
        solve(puzzle, resultProcessor);

        return (resultProcessor.getNumSolutions() == 1);
    }

    /**
     * Processor that merely count solutions
     */
    class CountingOnlyDLXResultProcessor implements DLXResultProcessor {
        private int numSolutions = 0;

        @Override
        public boolean processResult(DLXResult result) {
            numSolutions++;
            return true;
        }

        public int getNumSolutions() {
            return numSolutions;
        }
    }

    /**
     * Solve a Sudoku. The puzzle to be solved must be valid.
     * 
     * @param puzzle
     *            an array of 81 bytes. Zeroes signify empty cells
     */
    @Override
    public final void solve(byte[] puzzle) {
        final ColumnObject h = buildSparseArrayForPuzzle(puzzle);
        DLX.solve(h, true);
    }

    /**
     * Solve a Sudoku. The puzzle to be solved must be valid.
     * 
     * @param puzzle
     *            an array of 81 bytes. Zeroes signify empty cells
     * @param processor
     *            the processor used to handle results
     */
    public final void solve(byte[] puzzle, DLXResultProcessor processor) {
        final ColumnObject h = buildSparseArrayForPuzzle(puzzle);
        DLX.solve(h, true, processor);
    }

    /**
     * Prints out a puzzle to the PrintStream
     * 
     * @param out
     *            where to send the output
     * @param result
     *            a result generated by DLX.
     */
    public final void printPuzzle(PrintStream out, DLXResult result) {
        byte[] puzzle = new byte[81];
        puzzle = decodeDLXResult(result);
        SudokuUtils.printPuzzle(out, puzzle);
    }

    /**
     * Convert a DLXResult produced by solving a Sudoku, into an array that can
     * be used elsewhere.
     * 
     * @param result
     *            the DLXResult passed to a DLXResultProcessor
     * @return a solved Sudoku
     */
    public final byte[] decodeDLXResult(DLXResult result) {
        final Iterator<List<Object>> rows = result.rows();
        final byte[] puzzle = new byte[81];
        while (rows.hasNext()) {
            final List<Object> row = rows.next();
            byte r = -1; // canary values
            byte c = -1;
            byte v = -1;
            for (final Object obj : row) {
                if (obj instanceof CellValueLabel) {
                    final CellValueLabel cvl = (CellValueLabel) obj;
                    v = cvl.value;
                } else if (obj instanceof CellCoordinatesLabel) {
                    final CellCoordinatesLabel ccl = (CellCoordinatesLabel) obj;
                    r = ccl.row;
                    c = ccl.col;
                }
            }
            if ((v > -1) && (r > -1) && (c > -1)) {
                puzzle[r * 9 + c] = v;
            }
        }
        decodedResult = puzzle;
        return puzzle;
    }

    /**
     * From a supplied Sudoku puzzle, supply a sparse matrix to be fed into the
     * DLX algorithm.
     * 
     * @param puzzle
     *            a valid yet incomplete Sudoku puzzle
     * @return root of the sparse matrix
     */
    final ColumnObject buildSparseArrayForPuzzle(byte[] puzzle) {
        final byte[][] constraintSet = buildConstraintSets(puzzle);
        final ColumnObject obj = DLX.buildSparseMatrix(constraintSet, LABELS);
        sanityCheckSparseMatrix(obj);
        return obj;
    }

    /**
     * Make sure no columns are empty to begin with
     * 
     * @param constraintSet
     */
    final void sanityCheckSparseMatrix(ColumnObject obj) {
        ColumnObject curr = (ColumnObject) obj.R;
        while (curr != obj) {
            if (curr.size == 0) {
                System.err
                        .println("Empty column found! " + obj.name.toString());
            }
            curr = (ColumnObject) curr.R;
        }
    }

    /**
     * Given an incomplete yet valid puzzle grid, return an array of constraint
     * sets.
     * 
     * @param puzzle
     *            the incomplete, yet valid puzzle grid
     * @return an array of constraint sets
     */
    final byte[][] buildConstraintSets(byte[] puzzle) {
        final List<byte[]> constraintSets = new ArrayList<byte[]>(724);
        for (int j = 0; j < 9; ++j) {
            for (int i = 0; i < 9; ++i) {
                final byte curr = puzzle[j * 9 + i];
                if (curr > 0) {
                    // Cell is already occupied by a 'given'
                    final byte[] constraintSet = buildConstraintSet(j, i,
                            (curr - 1));
                    constraintSets.add(constraintSet);
                } else {
                    // Generate all possibilities for this cell
                    for (int val = 1; val <= 9; ++val) {
                        if (isMoveLegal(puzzle, j, i, val)) {
                            final byte[] constraintSet = buildConstraintSet(j,
                                    i, (val - 1));
                            constraintSets.add(constraintSet);
                        }
                    }
                }
            }
        }
        final byte[][] arrays = constraintSets.toArray(new byte[][] {});
        return arrays;
    }

    /**
     * Pack possible value into a byte array, ready to be fed into DLX sparse
     * matrix generator.
     * 
     * @param row
     *            between 0 and 8
     * @param column
     *            between 0 and 8
     * @param value
     *            between 0 and 8
     * @return the packed constraint set, ready to be fed as a row into DLX
     */
    final byte[] buildConstraintSet(int row, int column, int value) {

        final byte[] buffer = new byte[BUF_SIZE];
        // cell occupied (81 possibilities)
        buffer[((row * 9) + column)] = 1;

        // column contains n (81 possibilities)
        buffer[COLUMN_CONTAINS_OFFSET + ((column * 9) + value)] = 1;

        // row contains n (81 possibilities)
        buffer[ROW_CONTAINS_OFFSET + ((row * 9) + value)] = 1;

        // region contains n (81 possibilities)
        final int region = getRegion(row, column);
        buffer[REGION_CONTAINS_OFFSET + ((region * 9) + value)] = 1;

        return buffer;
    }

    /**
     * Get the region number this set of coordinates belong to. Regions are
     * numbered 0 to 8.
     * 
     * @param row
     *            an integer, 0 to 8
     * @param column
     *            an integer, 0 to 8
     * @return a region number, 0 to 8
     */
    final int getRegion(int row, int column) {
        return (3 * (row / 3) + (column / 3));
    }

    /**
     * Generate a set of label objects suitable for running Sudoku over DLX.
     * This needs to be executed only once
     * 
     * @return a set of column labels usable with {@link DLX#solve()}.
     */
    final Object[] generateLabels() {
        final ColumnLabel[] labels = new ColumnLabel[BUF_SIZE];

        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                labels[i * 9 + j] = new CellCoordinatesLabel((byte) i, (byte) j);
            }
        }
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                labels[COLUMN_CONTAINS_OFFSET + (i * 9 + j)] = new ColumnValueLabel(
                        (byte) (j + 1));
            }
        }
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                labels[ROW_CONTAINS_OFFSET + (i * 9 + j)] = new RowValueLabel(
                        (byte) (j + 1));
            }
        }
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                labels[REGION_CONTAINS_OFFSET + (i * 9 + j)] = new RegionValueLabel(
                        (byte) (j + 1));
            }
        }

        return labels;
    }

    /**
     * Check to see whether or not a value about to be placed in the grid hasn't
     * already been placed in the grid in the same column, row or region.
     * 
     * @param puzzle
     *            an array containing 81 cells for the puzzle grid, row-major,
     *            column and row indexed from zero. Zero values signify an
     *            unoccupied cell, values 1 to 9 are occupied
     * @param row
     *            an integer, 0 to 8
     * @param col
     *            an integer, 0 to 8
     * @param value
     *            and integer, 1 to 9
     * @return whether or not the same value has been placed in a row, column or
     *         region
     */
    final boolean isMoveLegal(byte[] puzzle, int row, int col, int value) {

        final boolean result = true;
        final int region = getRegion(row, col);
        for (int i = 0; i < 9; ++i) {
            if ((puzzle[row * 9 + i] == value)
                    || (puzzle[i * 9 + col] == value)
                    || (puzzle[SudokuUtils.SUDOKU_GRID_REGION_MAP[region][i]] == value)) {
                return false;
            }
        }
        return result;
    }

    public byte[] getDLXResult() {
        return decodedResult;
    }

}

abstract class ColumnLabel {
}

class CellCoordinatesLabel extends ColumnLabel {
    byte row, col;

    public CellCoordinatesLabel(byte row, byte col) {
        this.row = row;
        this.col = col;
    }

    @Override
    public String toString() {
        return "RC=(" + row + "," + col + ")";
    }
}

abstract class CellValueLabel extends ColumnLabel {
    byte value;

    public abstract String getType();

    @Override
    public String toString() {
        return getType() + "<-" + value;
    }
}

class RowValueLabel extends CellValueLabel {
    public RowValueLabel(byte value) {
        this.value = value;
    }

    @Override
    public String getType() {
        return "row";
    }
}

class ColumnValueLabel extends CellValueLabel {
    public ColumnValueLabel(byte value) {
        this.value = value;
    }

    @Override
    public String getType() {
        return "column";
    }
}

class RegionValueLabel extends CellValueLabel {
    public RegionValueLabel(byte value) {
        this.value = value;
    }

    @Override
    public String getType() {
        return "region";
    }
}
